package com.zwh.algorithm.leetcode.difficulty;

import java.util.Arrays;

public class LeetCode629 {
    /** 2023-07-13   K 个逆序对数组
     * todo 给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。
     * todo 逆序对的定义如下：对于数组的第 i 个和第 j 个元素，如果满 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。
     * todo 说明: n 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。
     * @param args
     */
    public static void main(String[] args) {
        kInversePairs1(2,1);
        digit(1000);
    }

    /**
     * 时间复杂度：O(n*k)
     * 空间复杂度：O(n*k)
     */
    static int  mod = (int) 10e+7;
    public static int kInversePairs1(int n,int k){
        long[][] f = new long[n + 1][k + 1];
        long[][] sum = new long[n + 1][k + 1];
        f[1][0] = 1;
        Arrays.fill(sum[1],1);
        for (int i = 2; i <= n; i++){
            for (int j = 0; j <= k; j++) {
                f[i][j] = j < i ? sum[i - 1][j] : sum[i - 1][j] - sum[i - 1][j - (i - 1) - 1];
                f[i][j] = (f[i][j] + mod) % mod;
                sum[i][j] = j == 0 ? f[i][j] : sum[i][j - 1] + f[i][j];
                sum[i][j] = (sum[i][j] + mod) % mod;
            }
        }
        return (int)f[n][k];
    }

    public static int kInversePairs2(int n, int k) {
        int[][] f = new int[n + 1][k + 1];
        int[][] sum = new int[n + 1][k + 1];
        f[1][0] = 1;
        Arrays.fill(sum[1], 1);
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                f[i][j] = j < i ? sum[i - 1][j] : (sum[i - 1][j] - sum[i - 1][j - (i - 1) - 1] + mod) % mod;
                sum[i][j] = j == 0 ? f[i][j] : (sum[i][j - 1] + f[i][j]) % mod;
            }
        }
        return f[n][k];
    }

    public static int digit(int x){
        String s = String.valueOf(x);
        System.out.println(s);
        char[] c = s.toCharArray();
        System.out.println(c);
        String a = "";
        for (int i = s.length()-1; i >= 0; i--) {
             a +=c[i];
        }
        System.out.println(a);
        return Integer.valueOf(a);
    }
}
